package gold.digger;

import gold.utils.InputUtil;

import java.util.*;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC1046 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {
        public int lastStoneWeight(int[] stones) {
            TreeMap<Integer, Integer> set = new TreeMap<>();
            for (int stone : stones) {
                set.put(stone, set.getOrDefault(stone, 0) + 1);
            }

            while (set.size() > 1 || (set.size() == 1 && set.get(set.lastKey()) >= 2)) {
                int first = set.lastKey();
                int firstCount = set.get(first);
                if (firstCount >= 2) {
                    if (firstCount == 2) set.remove(first);
                    else set.put(first, firstCount - 2);
                    set.put(0, set.getOrDefault(0, 0) + 1);
                    continue;
                } else {
                    //数量只有1
                    set.remove(first);
                    int second = set.lastKey();
                    int secondCount = set.get(second);
                    if (secondCount == 1) set.remove(second);
                    else set.put(second, secondCount - 1);
                    set.put(first - second, set.getOrDefault(first - second, 0) + 1);
                }
            }

            return set.lastKey();
        }
    }

    public void run() {
        Solution solution = new Solution();
        int[] arr = InputUtil.toIntegerArray("[2,2,2,3]");
        System.out.println(solution.lastStoneWeight(arr));
    }

    public static void main(String[] args) throws Exception {
        LC1046 an = new LC1046();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
